%----------------------------------------------------------------------------------------
%	CHAPTER 8
%----------------------------------------------------------------------------------------

\chapter{优化处理}

在实际开发编译器时，对于前端技术，近年来一直比较稳定，以语法制导、形式语言自动机为基础，更多强调的是语法制导技术的翻译与分析，到中间代码生成为止，编译器基础的算法已经介绍完毕。对于后端技术，发展十分迅猛，是现代编译器工程实现中相当重要的部分。后端是一个从中间代码到目标代码的生成系统，由两部分构成：一是\textbf{优化处理}，给定中间代码，加快代码执行效率，减小空间占用；二是\textbf{目标代码生成}，在优化处理的基础上，生成精简高效的目标代码。前端决定了编译器能否实现，后端则决定了编译器是否可用。

本章主要介绍优化处理，优化是编译器中一个重要环节，优化的设计在整个编译器设计过程中占据相当大的比重，目的是\textbf{产生更高效的目标代码}。优化处理中包括大量数据结构、算法的优化，本书不做详细展开，本章主要介绍优化的基本思想和几种优化方法。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{优化的分类}

优化处理可以在不同层面上进行，可分为在源代码或中间代码级上进行的与机器无关的优化，以及在目标代码级上进行的与机器有关的优化。

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{与机器无关的优化}

不采用与目标机相关的知识，如果优化在各个机器上都可以进行，就是与机器无关的优化。由于每一条中间代码指令都是一个单操作，在中间代码级上优化比较容易。在源代码级的优化相对困难，可以在编写程序时实现。

\begin{itemize}
\item \textbf{全局优化：}针对整个源程序，能达到更好的优化效果，实现难度更大。
\item \textbf{局部优化：}除全局优化以外，处理局部的函数和程序块，更易实现。
\end{itemize}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{与机器有关的优化}

需要考虑目标机的性质。目标代码生成是从四元式生成目标代码，如果不考虑优化，是一对一的映射过程，是有模板的映射，而考虑优化则需要处理大量问题。

\begin{itemize}
\item \textbf{寄存器分配优化：}现代CPU的设计，包括操作系统和编译器，都要考虑目标机关于存储器的分配。寄存器访问速度快，运算效率高，但资源有限，设计相关算法合理分配寄存器能够大大优化效率。
\item \textbf{消除无用代码优化：}例如一些无用跳转，可以依据目标机进行。
\end{itemize}

以上这两类优化处理方法中，主要介绍局部优化（第八章）和寄存器分配优化（第九章）。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{常见的几种局部优化方法}

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{常值表达式节省（常数合并）}

如：$a=5+3; b=a+1; \dots$

等号右边的表达式$5+3$和$a+1$都是常值表达式，$a$和$b$的值不需要在程序运行时进行计算，编译器会将其优化为$a=8; b=9;$的形式，这样的优化被称为\textbf{常值表达式节省}。这种方法看似简单，却十分关键，节省了大量无用计算，若没有这种技术，现代计算机会慢10倍，编写的程序中需要进行大量常数合并，是一种常见的优化形式。

注：若$a=5+3;\dots;a=x\dots; a=a+1;$ $a=5+3$中的$a$是常数，后$a$经过赋值，$a=a+1$中的$a$不再是常数，$a+1$不是常值表达式。

\subsection{公共表达式节省（删除多余运算）}

如：$a=b*d+1; e=b*d-2;\dots$

等号右边的两个表达式中都有$b*d$，且$b$和$d$的值在使用前后没有被修改，则$b*d$是公共表达式，不用重复计算，可以优化为$t=b*d; a=t+1; e=t-2;$的形式，减少了一次乘法，增加了一次赋值，乘法的计算代价高于赋值，这样的形式达到了优化的目的。

注：若$b=b*d+1; e=b*d-2$;就不能再使用这样的方法，因为第一个赋值表达式中，修改了$b$的值，公共表达式要求表达式中的变量不变，所以此处的$b*d$不是公共表达式。

\subsection{删除无用赋值}

 如：$a=b+c; x=d-e; y=b; a=e-h/5;$

看似没有问题，仔细观察在$a$的两次赋值之间，没有对$a$的应用，则前一次对$a$的赋值$a=b+c$为无用赋值。可以将第一个式子删除，优化为$x=d-e; y=b; a=e-h/5;$的形式。

\subsection{不变表达式外提（循环优化之一：把循环不变运算提到循环外）}

如：$i=1; \text{while} (i<100)\enspace{x=(k+a)/i; i++;}$

假设循环体中$k$和$a$的值都没有改变，则每一次循环中$k+a$的值都不变，将其称为循环不变表达式。如果每次循环中，都计算一遍$k+a$，循环次数非常多时，计算代价将非常高。因此，可以优化为$i=1; t=k+a; \text{while}(i<100)\enspace{x=t/i;\dots; i++;}$的形式。

不变表达式外提也是一种常见的优化方法。如何通过算法实现找出不变表达式并外提，也是一个需要解决的问题。

\subsection{消减运算强度（循环优化之二：把运算强度大的运算换算成强度小的运算）}

如：$i=1; \text{while}(i<100)\enspace{t=4*i; b=a↑2;i++;}$

幂运算强度大于乘除取模运算，乘除取模运算强度大于加减赋值运算。$a↑2$为$a$的平方，循环变量$i$每次加1，$4*i$的结果为4, 8, 12, \dots 的等差数列，每次乘法的效果和每次加4的效果一致。因此，可以优化为$i=1; t=4*i; \text{while}(i<100)\enspace{t=t+4; b=a*a;\dots;i++;}$的形式。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------

\section{局部优化算法探讨}

通过以上例子，我们对优化有了一定感性的认识，接下来进一步系统地进行探讨。在编译器设计中，局部优化算法是以\textbf{基本块}为单位进行的，\textbf{基本块}也是目标代码生成的基本单位。

%----------------------------------------------
\begin{definition}基本块
\begin{tcolorbox}[colback=yellow!15!white,colframe=yellow!75!black]
程序中一段顺序执行的语句序列，其中只有一个入口和一个出口。
\end{tcolorbox}
\label{def:8-1}
\end{definition}
%----------------------------------------------

根据定义中的“顺序执行”、“一个入口，一个出口”，自然联想到，基本块的划分与条件判断以及跳转语句有关。执行一个基本块内的程序，只能从第一条顺序执行到最后一条，不存在其他入口或出口。满足这样要求的程序段称为一个独立的基本块。根据定义，只要找到基本块的入口和出口，就能找到基本块。

\subsection[基本块划分算法]{基本块划分算法}

\begin{enumerate}
\item \textbf{找出基本快的入口语句:}（以下为两种判断条件，满足其一即可）

\begin{itemize}
\item 程序的第一个语句或转向语句转移到的语句，四元式中的转向语句包括goto、then、else (无条件跳)、do (循环体中)。
\item 紧跟在转向语句后面的语句。
\end{itemize}

\item \textbf{对每一入口语句，构造其所属的基本块:}

\begin{itemize}
\item 从该入口语句到另一入口语句之间的语句序列；
\item 从该入口语句到另一转移语句（或停止语句）之间的语句序列。
\end{itemize}

\end{enumerate}

%-------------------------------------------
\begin{example}
条件语句四元式如下，给出基本块划分：

\begin{tabular}{p{1.6em}p{1.7em}*{2}{p{0.5em}}}
gt(E)\\
(then,&res(E),&\_\_,&\_\_)\\
gt($\text{S}_{1}$)\\
(else,&\enspace\enspace\_\_,&\_\_,&\_\_)\\
gt($\text{S}_{2}$)\\
(ifend, &\enspace\enspace\_\_,&\_\_,&\_\_)
\end{tabular}


解：语句，无外乎逻辑以及逻辑下的具体操作。其中gt($\text{S}_{1}$)和gt($\text{S}_{2}$)均为完整语义块，若不考虑嵌套条件语句，gt($\text{S}_{1}$)和gt($\text{S}_{2}$)均为顺序执行。因此给出的四元式中，包含gt(E) (then, res(E), \_\_, \_\_)，gt($\text{S}_{1}$) (else, \_\_, \_\_, \_\_)和gt($\text{S}_{2}$) (ifend, \_\_, \_\_, \_\_)三个基本块，入口语句为第一个语句或转移语句的后一句，一直到另一转移语句结束。
\label{ex:8-1}
\end{example}
%-------------------------------------------

%-------------------------------------------
\begin{example}
设有源程序片段，给出基本块划分：

$x = 1;$

$a:\enspace r =x*5;$

$\text{if}(x<10)$

$x=x+1;$

$\text{goto} \enspace a;$

$r=0;$


解：goto语句在编程中不建议大家使用，但有助于理解编译器。
第一步，写出对应的四元式序列如图\ref{fig:8-1}，其中的赋值语句是以单操作形式，最左侧为结果单元。goto语句对应的四元式，定义操作符为gt，表示直接跳转。lb四元式表示跳转的目标，因此将它作为基本块的开始。if四元式等价于前面介绍的(then, res(E), \_\_, \_\_)。ie四元式是转向语句转移到的语句，作为基本块的开始。

%-------------------------------------------
\begin{figure}[htbp]
\centering
    \begin{minipage}[t]{0.45\textwidth}
	\centering
	\input{chapter8/figures/corresponding_quadratic_sequence}
	\caption[]{对应的四元式序列}
	\label{fig:8-1}
	\end{minipage}
    \begin{minipage}[t]{0.45\textwidth}
	\centering
    \input{chapter8/figures/program_flow_graph_with_basic_blocks_as_nodes}
	\caption[]{以基本块为节点的程序流图}
	\label{fig:8-2}
	\end{minipage}
\end{figure}
%-------------------------------------------

第二步，划分基本块。根据算法，找出所有入口，两入口之间的部分即为基本块。观察四元式序列，第(1)个四元式是程序入口，是基本块的入口语句；第(2)个四元式是第(9)个四元式跳转到的语句，可以作为基本块的入口；第(3)到第(5)个四元式，根据定义，都不是基本块入口；第(6)个四元式，是跳转语句，不是基本块入口，但跳转语句的下一条，即第(7)个四元式是基本块入口；第(8)个四元式不是基本块入口；第(9)个四元式是跳转语句，不是基本块入口，下一个四元式(10)是基本块入口。从而划分得到如下四个基本块，如图\ref{fig:8-2}。
\label{ex:8-2}
\end{example}
%-------------------------------------------

\subsection[局部优化示例]{局部优化示例}

%-------------------------------------------
\begin{example}
基本块内设有语句片段：

$\text{B}=5;\enspace \text{A}=2*3.14/(\text{R}+\text{r})$;

$\text{B}=2*3.14/(\text{R}+\text{r})*(\text{R}-\text{r})$;

解：这是一个基本块，优化后结果如下。第一个式子删除对B的无用赋值；第二个式子可进行常值表达式节省，$2*3.14$可优化为$6.28$；第二个式子和第三个式子中都出现了$2*3.14/(\text{R}+\text{r})$，可以进行公共表达式节省，第二个式子中替换为A。

$\text{A}=6.28/(\text{R}+\text{r})$;

$\text{B}=\text{A}*(\text{R}-\text{r})$;

上述是人工优化的思考过程，下面系统地进行优化。

\begin{itemize}
\item 第一步，根据原语句片段，生成图\ref{fig:8-3}左侧四元式序列。
\item 第二步，逐个观察四元式。

第(1)个四元式，没有可优化的。

第(2)个四元式，是常值表达式，可以优化为$t_{1}=6.28$，保存该值，不生成四元式。

第(3)个四元式，$\text{R}+\text{r}$必须计算，不能优化。

第(4)个四元式，将$t_{1}$替换为$6.28$。

第(5)个四元式不能优化。

第(6)个四元式，与第(2)个四元式相同，优化为$t_{4}=6.28$并保存。

第(7)个四元式,与第(3)个四元式运算、运算对象相同，是公共表达式，保留$t_{5}≡t_{2}$的关系。

第(8)个四元式，$t_{4}$用$6.28$替代，$t_{5}$用$t_{2}$替代，与第(4)个四元式有公共表达式，保留$t_{6}≡t_{3}$的关系。

第(9)个四元式不能优化。

第(10)个四元式中的$t_{6}$用$t_{3}$代替。

第(11)个四元式赋值给B。

得到结果如图\ref{fig:8-3}右侧，相较原四元式序列，省去了四条。

\item 第三步：继续观察四元式。B的两次赋值之间（第(2)到第(10)个四元式中），B没有引用，因此删除第(1)个四元式中的无用赋值B。
\end{itemize}

\indent 最终得到优化后6个四元式序列，优化过程如图\ref{fig:8-3}所示。

%-------------------------------------------
\begin{figure}[htbp]
\centering
\input{chapter8/figures/process_of_quadratic_sequence_optimization}
\caption[]{四元式序列的优化过程}
\label{fig:8-3}
\end{figure}
%-------------------------------------------

\indent 根据例\ref{ex:8-3}总结优化的基本算法设计：

\begin{enumerate}
\item 对于常值表达式节省（例中(2)(6)）\\
(1)先进行常值计算；\\
(2)取常值的变量以常值代之；

\item 公共表达式节省（例中(7)(8)）\\
(1)找公共表达式，建立结果变量等价关系；\\
(2)等价变量以老变量代替新变量；

\item 删除无用赋值（例中(1)）\\
(1)确认一个变量两个赋值点间无引用点；\\
(2)则前一赋值点为无用赋值；

\dots\dots
\end{enumerate}

\label{ex:8-3}
\end{example}
接下来，进一步构造算法解决这些问题。

%----------------------------------------------------------------------------------------
%    NEW SECTION
%----------------------------------------------------------------------------------------
\section{基于DAG的局部优化方法}

DAG (Directed Acyclic Graph)是指无环有向图，或称有向无环图（如图\ref{fig:8-4}），对于计算机相关的系统开发及研究十分重要，这里用来对基本块内的\textbf{四元式序列进行优化}。

%-------------------------------------------
\begin{figure}[htbp]
\centering
\input{chapter8/figures/DAG}
\caption[]{有向无环图}
\label{fig:8-4}
\end{figure}
%-------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{四元式序列的DAG表示}

如何把线性的四元式映射到图结构呢？下面图\ref{fig:8-5}给出DAG的结点内容及其表达。图中包含结点，因为是有向图，又包含前驱和后继。四元式中包含一个运算符，两个运算对象，一个结果单元。有向无环图的要素如何与四元式的要素对应起来，这是要研究的第一个问题。

%-------------------------------------------
\begin{figure}[htbp]
\centering
\input{chapter8/figures/pre_next}
\caption[]{结点的前驱和后继}
\label{fig:8-5}
\end{figure}
%-------------------------------------------


\begin{enumerate}
\item \textbf{DAG的结点内容及其表示}

\begin{itemize}
\item $n_i$：\textbf{结点的编码}；
\item ω：\textbf{运算符},置于结点左侧，将该结点称为ω运算结点，代表ω运算。ω运算的运算对象为其后继节点，结果单元标记在结点右侧；
\item M：\textbf{主标记}，使用时作为代表优先被使用，如果是叶子结点，表示变量和常数的初值；
\item $\text{A}_{i}$：\textbf{附加标记}，为运算结果变量，为便于描述等价关系，可设置多个，$i=1, 2, 3, \dots$。如例\ref{ex:8-3}中$t_{2}$和$t_{5}$都表示$\text{R}+\text{r}$的结果，可以$t_{2}$为主标记，$t_{5}$为附加标记，从而便于描述等价关系。

右图中值为ω运算结果超过一个变量，M, $\text{A}_{1}, \text{A}_{2}, \text{A}_{3}$都取ω运算结果值，它们都应放在结点右侧。在M, $\text{A}_{1}, \text{A}_{2}, \text{A}_{3}$中选择M作为\textbf{主标记}，主标记之外的运算结果变量称为\textbf{附加标记}，$\text{A}_{1}, \text{A}_{2}, \text{A}_{3}$均与M等价。
\end{itemize}

\item \textbf{四元式的DAG表示}

\begin{itemize}
\item \textbf{赋值}：赋值四元式(= B \_\_ A)或A=B，将B的值赋给A，表示A和B是等价的。DAG表示为\tikz [nodes={anchor=west, inner sep=0em}] {\node [circle, draw, minimum size=1.2em] (n1) {$n_i$}; \node [right=0em of n1, yshift=-0.2em] {B|A};}，省去了赋值运算符，B为主标记，A为附加标记。

\item \textbf{双目运算：}双目运算四元式(ω B C A)或A = BωC，将BωC赋值给A，其中ω可以是算术运算、关系运算、逻辑运算等。DAG表示为 \tikz {\matrix [matrix of nodes, nodes in empty cells, nodes={anchor=west, inner sep=0em, minimum size=1.2em, }]{ & \node[circle, draw](n3){$n_3$}; & \\ \node[circle, draw, yshift=-1em](n1){$n_1$}; & & \node[circle, draw, yshift=-1em](n2){$n_2$};\\};\node[left=0em of n3.west]{ω};\node[right=0em of n3.east]{A};\node[right=0em of n1.east]{B};\node[right=0em of n2.east]{C};\draw[-](n3)--(n1); \draw[-](n3)--(n2);}，ω运算符放在结点$n_3$左侧，结果单元A放在结点$n_3$右侧，两个运算对象B和C放在下面结点$n_1$和$n_2$的右侧，作为$n_3$的后继结点，通过ω运算赋值给A。

\item \textbf{单目运算：}有单目运算四元式(ω B \_\_ A)或A =ωB。与双目运算类似，从原来的二叉变成“一叉”，DAG表示为\tikz{\matrix[nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&\node[circle,draw](n2){$n_2$};\\\node[circle,draw,yshift=-1em](n1){$n_1$};&\\};\node[left=0em of n2]{ω};\node[right=0em of n2]{A};\node[right=0em of n1]{B};\draw[-](n2)--(n1);}。结点$n_1$表示B，通过ω运算赋值给A。

\item \textbf{下标变量赋值运算：}。有下标变量赋值运算四元式A=B[C]，DAG表示为\tikz {\matrix [matrix of nodes, nodes in empty cells, nodes={anchor=west, inner sep=0em, minimum size=1.2em, }]{ & \node[circle, draw](n3){$n_3$}; & \\ \node[circle, draw, yshift=-1em](n1){$n_1$}; & & \node[circle, draw, yshift=-1em](n2){$n_2$};\\};\node[left=0em of n3.west]{[ ]};\node[right=0em of n3.east]{A};\node[right=0em of n1.east]{B};\node[right=0em of n2.east]{C};\draw[-](n3)--(n1); \draw[-](n3)--(n2);}。A有两个后继B和C，[]表示按变量C为偏移量，取变量B对应数组的元素，结果用A表示。将变量赋值给数组元素B[C]=D，DAG表示为\tikz {\matrix [matrix of nodes, nodes in empty cells, nodes={anchor=west, inner sep=0em, minimum size=1.2em, }]{ && \node[circle, draw](n4){$n_4$}; & \\ \node[circle, draw, yshift=-1em](n1){$n_1$}; & & \node[circle, draw, yshift=-1em](n2){$n_2$};&& \node[circle, draw, yshift=-1em](n3){$n_3$};\\};\node[left=0em of n4.west]{[ ]};\node[right=0em of n3.east]{D};\node[right=0em of n1.east]{B};\node[right=0em of n2.east]{C};\draw[-](n4)--(n1); \draw[-](n4)--(n2);\draw[-](n4)--(n3);}。这种情况比较特殊，[]操作对象不是B、C、D中任何一个，而是以B指针开始，以C对应的变量为偏移，并以D赋值，因此结点$n_4$右侧没有出现结果单元，而是用这个结构表示赋值的过程。

\item \textbf{转向：}有转向四元式(ω [B] \_\_ A)，B为可选单元，DAG表示如下：第一个表示无条件跳转到A\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](ni){$n_i$};\node[left=0em of ni]{ω};\node[right=0em of ni]{A}}，第二个根据B进行跳转\tikz{\matrix[nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&\node[circle,draw](n2){$n_2$};\\\node[circle,draw,yshift=-1em](n1){$n_1$};&\\};\node[left=0em of n2]{ω};\node[right=0em of n2]{A};\node[right=0em of n1]{B};\draw[-](n2)--(n1);}
。
\end{itemize}

\end{enumerate}

有了这样的表示形式，就能够完成对四元式序列的DAG表示。

%-------------------------------------------
\begin{example}
	
求下述语句片段的DAG表示：

$\text{B}=5; \text{A}=2*3.14*(\text{R}+\text{r}); \text{B}=2*3.14*(\text{R}+\text{r})/(\text{R}-\text{r});$

解：
\begin{itemize}
\item 第一步，生成对应的四元式序列。

\begin{tabular}{lll}
(1) $\text{B}=5$ &(2) $t_{1}=2*3.14$ &(3) $t_{2}=\text{R}+\text{r}$ \\
(4) $t_{3}=t_{1}*t_{2}$ &(5) $\text{A}=t_{3}$ &(6) $t_{4}=2*3.14$ \\
(7) $t_{5}=\text{R}+\text{r}$ &(8) $t_{6}=t_{4}*t_{5}$ &(9) $t_{7}=\text{R}-\text{r}$ \\
(10) $t_{8}=t_{6}/t_{7}$ &(11) $\text{B}=t_{8}$	
\end{tabular}


\item 第二步，逐个扫描四元式，构建优化DAG图。

第(1)个赋值四元式，创建结点1\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){1};\node[right=0em of n1]{5|B}}，主标记为5，附加标记为B，表示$\text{B}=5$。

第(2)个常值运算四元式，将2*3.14化简为6.28，创建结点2\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){2};\node[right=0em of n1]{6.28|$t_{1}$}}，与结点1类似，主标记为6.28，附加标记为$t_{1}$。

第(3)个四元式，R和r在DAG中均未出现，创建结点3、4表示R和r，再创建结点5，表示通过加法操作结点3和4的主标记，结果保存在$t_{2}$ \tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&\node[circle,draw](n5){5};\\\node[circle,draw,yshift=-1em](n3){3};&&\node[circle,draw,yshift=-1em](n4){4};\\};\node[left=0em of n5]{+};\node[right=0em of n5]{$t_2$};\node[right=0em of n3]{R};\node[right=0em of n4]{r};\draw[-](n5)--(n3);\draw[-](n5)--(n4);}。

第(4)个四元式，$t_{1}$在结点2，$t_{2}$在结点5，创建结点6，操作结点2和5的主标记进行乘法运算，赋值给$t_{3}$\tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&\node[circle,draw](n6){6};\\\node[circle,draw,yshift=-1em](n2){2};&&\node[circle,draw](n5){5};\\};\node[left=0em of n6]{*};\node[right=0em of n6]{$t_{3}$};\node[right=0em of n2]{6.28|$t_{1}$};\node[right=0em of n5]{$t_{2}$};\node[left=0em of n5]{+};\draw[-](n5)--(n6);\draw[-](n6)--(n2);}。

第(5)个四元式，将$t_{3}$赋值给A，$t_{3}$在DAG中已存在，因此A作为结点6的附加标记\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){6};\node[right=0em of n1]{$t_{3}$|A};\node[left=0em of n1]{*};}。注意，因为主标记$t_{3}$为临时变量，而A为用户定义变量，这里要将A和$t_{3}$进行互换，表示为\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){6};\node[right=0em of n1]{A|$t_{3}$};\node[left=0em of n1]{*};}。

第(6)个四元式，将6.28赋值给$t_{4}$，6.28在DAG中已存在，因此$t_{4}$作为结点2的附加标记\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){6};\node[right=0em of n1]{6.28|$t_{1}$,$t_{4}$};}。

第(7)个四元式，将$\text{R}+\text{r}$赋值给$t_{5}$，R和r以及$\text{R}+\text{r}$的结果在DAG中也已存在，因此将$t_{5}$作为结点5的附加标记\tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&\node[circle,draw](n5){5};\\\node[circle,draw,yshift=-1em](n3){3};&&\node[circle,draw,yshift=-1em](n4){4};\\};\node[left=0em of n5]{+};\node[left=0em of n5,yshift=-1.5ex]{$t_{4}$};\node[right=0em of n5]{$t_{2}$|$t_{5}$};\node[right=0em of n3]{R};\node[right=0em of n4]{r};\draw[-](n5)--(n3);\draw[-](n5)--(n4);}
。

第(8)个四元式，$t_{4}$在结点2，$t_{5}$在结点5，结点2和结点5的乘法结果在DAG中已存在，因此将$t_{6}$作为结点6的附加标记\tikz{\node[anchor=base,inner sep=0em,minimum size=1.2em]{A|$t_{3}$,$t_{6}$};}
。

第(9)个四元式，R在结点3，r在结点4，$\text{R}-\text{r}$的结果不存在，因此创建结点7，$\text{R}-\text{r}$的结果保存在$t_{7}$\tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&\node[circle,draw](n7){7};\\\node[circle,draw,yshift=-1em](n3){3};&&\node[circle,draw,yshift=-1em](n4){4};\\};\node[left=0em of n5]{-};\node[right=0em of n7]{$t_{7}$};\node[right=0em of n3]{R};\node[right=0em of n4]{r};\draw[-](n7)--(n3);\draw[-](n7)--(n4);}
。

第(10)个四元式，$t_{6}$在结点6，$t_{7}$在结点7，创建结点8，表示结点6的主标记和结点7的主标记相除，结果保存在$t_{8}$\tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&&\node[circle,draw](n8){8};&\\\node[circle,draw](n6){6};&&&&\node[circle,draw,yshift=-1em](n7){7};\\};\node[left=0em of n8]{/};\node[right=0em of n8]{$t_{8}$};\node[left=0em of n6]{*};\node[right=0em of n6]{A|$t_{3}$,$t_{6}$};\node[right=0em of n7]{$t_{7}$};\node[left=0em of n7]{-};\draw[-](n8)--(n6);\draw[-](n8)--(n7);}。

第(11)个四元式，将$t_{8}$赋值给B，在结点1中删去B
\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){1};\node[right=0em of n1]{5|\bcancel{B}}}
，将B作为结点8的附加标记\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){8};\node[right=0em of n1]{$t_{8}$|B};\node[left=0em of n1]{/};}，同样需要调换B和$t_{8}$的顺序\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){8};\node[right=0em of n1]{B|$t_{8}$};\node[left=0em of n1]{/};}。

得到最终的DAG表示如下：

%----------------------------------------------
\begin{figure}[htbp]
\centering
\input{chapter8/figures/final_DAG}
\caption[]{最终的DAG表示}
\label{fig:8-6}
\end{figure}
%----------------------------------------------

\item 第三步，根据优化的DAG重组四元式。

结点1，没有后继结点，即没有运算四元式，附加标记的B被删去，若存在附加标记，表示存在赋值四元式。

结点2，没有后继结点，没有运算四元式，但存在等价关系，理论上生成$t_{1}=6.28$和$t_{4}=6.28$两个赋值四元式，但$t_{1}$和$t_{4}$是临时变量，是编译器定义的，与用户无关，临时变量不会在后续被使用，且$t_{1}$、$t_{4}$与6.28等价，因此可以用6.28代替$t_{1}$和$t_{4}$，附加标记中放的都是临时变量，这时的赋值四元式可以省去。

结点3和结点4，没有后继结点，没有附加标记，不需要进行操作。

结点5，存在后继结点，生成运算四元式$t_{2}=\text{R}+\text{r}$，附加标记上的临时变量不用生成赋值语句，因此具有等价关系的$t_{5}$被省去。

结点6，存在后继结点，生成运算四元式$\text{A}=6.28*t_{2}$，附加标记$t_{3}$、$t_{6}$均为临时变量，省去。

结点7，存在后继结点，生成运算四元式$t_{7}=\text{R}-\text{r}$。

结点8，存在后继结点，生成运算四元式$\text{B}=\text{A}/t_{7}$。

最终得到重组四元式如下，四元式数量从原来的11减少为4。


(1) $t_{2}=\text{R}+\text{r}$

(2) $\text{A}=6.28*t_{2}$

(3) $t_{7}=\text{R}-\text{r}$

(4) $B=\text{A}/t_{7}$

\end{itemize}
介绍到这里，第二步中对于结点6和结点8，为什么要进行位置交换？其实目的是减少四元式数量，优化中间代码。当结点右部存在若干个等价的值（包括常值、变量），在这若干个中选择一个作为主标记，优先关系为：常值（第一级）、用户定义变量（第二级）、临时变量（第三级）。如果附加标记中都是临时变量，赋值四元式可以省去；如果附加标记中存在用户定义变量，赋值四元式不可省去，因为在后续可能会被用户使用。结点1中B在附加标记上，且被重新赋值，原来的B可被主标记值替代，因此被省去，若B在主标记上，则不可省去。
\label{ex:8-4}
\end{example}
%----------------------------------------------

%----------------------------------------------------------------------------------------
%    NEW SUB-SECTION
%----------------------------------------------------------------------------------------

\subsection{基于DAG的局部优化算法}

例\ref{ex:8-4}是一个典型的DAG优化算法实例，下面对基于DAG的局部优化算法进行系统总结。

1.\textbf{构造基本块内优化的DAG}

假设：\ding{172}$n_i$为已知结点号，n为新结点号；\ding{173}访问各节点信息时，按结点号逆序进行；具体原因后面在例题中说明。

\begin{itemize}
\item 开始：

\ding{172}DAG置空；依次读取一四元式A=BωC。

\ding{173}分别定义B, C结点，若已定义过，可以直接使用。

(1) 若赋值四元式$\text{A}=\text{B}$

\ding{172}把A附加于B上，即\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){$n_1$};\node[right=0em of n1]{\dots B\dots,A}}，表示A和B等价。

\ding{173}若A在$n_2$已定义过，且A在附加标记时，需要删去，即\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n2){$n_2$};\node[right=0em of n2]{\ldots |\ldots \bcancel{A\ldots}}}；A在主标记时，则无需删去。

(2)	若常值表达式A=$\text{C}_{1}$ω$\text{C}_{2}$或$\text{A}=\text{C}$

\ding{172}计算常值$\text{C}=\text{C}_{1}$ω$\text{C}_{2}$。

\ding{173}若C在$n_1$已定义过，则\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){$n_1$};\node[right=0em of n1]{C|\ldots ,A}}，如上例中结点2的主标记为6.28，表示$t_{4}=6.28$时，只需将$t_{4}$作为这个结点的附加标记；否则申请新结点，且\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n){$n$};\node[right=0em of n]{C|A}}，C为主标记，A为附加标记。

\ding{174}若A在$n_2$已定义过，且A在附加标记，删去，即\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n2){$n_2$};\node[right=0em of n2]{\ldots |\ldots \bcancel{A\ldots}}}。

(3)	若其他表达式$\text{A}=\text{BωC}$或$\text{A}=\text{ωB}$

\ding{172}若在$n_1$存在公共表达式BωC或ωB，分别表示为\tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&&\node[circle,draw](n1){$n_1$};&&\\\node[circle,draw,yshift=-1em](ni){$n_i$};&&&&\node[circle,draw,yshift=-1em](nj){$n_j$};\\};\node[left=0em of n1]{ω};\node[right=0em of n1]{\ldots};\node[right=0em of ni]{\ldots B\ldots};\node[right=0em of nj]{\ldots C\ldots};\draw[-](ni)--(n1);\draw[-](nj)--(n1);}和\tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&&\node[circle,draw](n1){$n_1$};\\\node[circle,draw,yshift=-1em](ni){$n_i$};&&\\};\node[left=0em of n1]{ω};\node[right=0em of n1]{\ldots};\node[right=0em of ni]{\ldots B\ldots};\draw[-](ni)--(n1);}，则把A附加在$n_1$上，即\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){$n_1$};\node[right=0em of n1]{\ldots ,A};\node[left=0em of n1]{ω};}。
                    
\ding{173}若不存在公共表达式，则申请新结点n，\tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&&\node[circle,draw](n1){$n_1$};&&\\\node[circle,draw,yshift=-1em](ni){$n_i$};&&&&\node[circle,draw,yshift=-1em](nj){$n_j$};\\};\node[left=0em of n1]{ω};\node[right=0em of n1]{A};\node[right=0em of ni]{\ldots B\ldots};\node[right=0em of nj]{\ldots C};\draw[-](ni)--(n1);\draw[-](nj)--(n1);}或\tikz{\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&&\node[circle,draw](n1){$n_1$};\\\node[circle,draw,yshift=-1em](ni){$n_i$};&&\\};\node[left=0em of n1]{ω};\node[right=0em of n1]{A};\node[right=0em of ni]{\ldots B\ldots};\draw[-](ni)--(n1);}。

\ding{174}若A在$n2$已定义过，且A在附加标记，则删除，即\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n2){$n_2$};\node[right=0em of n2]{\ldots |\ldots \bcancel{A\ldots}}}；若A为主标记，则免删。

\item 结束：调整结果单元结点的主标记、附加标记的顺序。

$\bigstar$主标记优先顺序为：\textbf{常量，非临时变量，临时变量}。

\end{itemize}

2.\textbf{根据基本块内优化的DAG，重组四元式}

假设：\ding{172}\textbf{临时变量}的作用域是基本块内；\ding{173}\textbf{非临时变量}的作用域也可以是基本块外。

两条假设的目的是在最终优化后的代码中，必须保证所有非临时变量的值是最新的，临时变量的值若在后续没有使用，就不需要赋值。

\begin{itemize}
\item 开始：按结点编码顺序，依次读取每一结点n1信息：

(1) 若$n_1$为带有附加标记的叶结点，即\tikz{\node[anchor=west,inner sep=0em,minimum size=1.2em,circle,draw](n1){$n_1$};\node[right=0em of n1]{B|A\tiny{1}\normalsize{,A}\tiny{2}\normalsize{,\ldots}}}
，表示$\text{A}_{i}$与B等价

\ding{172}若$\text{A}_{i}$为非临时变量，则生成$q_1$: $\text{A}_{i}=\text{B}(i=1, 2,…)$。

\ding{173}若$\text{A}_{i}$是临时变量，则不需要生成。临时变量在基本块外不使用，而生成四元式时使用的是主标记B。

(2)	若$n_1$为带有附加标记的非叶结点，即\tikz{\draw[rounded corners=2pt,fill={rgb,255:red,255;green,230;blue,230},draw opacity=0.2](0.1, -0.1) rectangle (2,-0.75);\matrix[matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}]{&&\node[circle,draw](n1){$n_1$};&&\\\node[circle,draw,yshift=-1em](ni){$n_i$};&&&&\node[circle,draw,yshift=-1em](nj){$n_j$};\\};\node[left=0em of n1]{ω};\node[right=0em of n1]{A|A\tiny{1}\normalsize{,A}\tiny{2}\normalsize{,}};\node[right=0em of ni,xshift=-.2em]{B|\ldots};\node[right=0em of nj](njr){C|\ldots};\node[left=-0.2em of nj](njl){\ldots};\draw[-](ni)--(n1);\draw[-](nj)--(n1);}

\ding{172}生成$q_1$: A=BωC或A=ωB，用主标记进行计算。

\ding{173}若$\text{A}_{i}$为非临时变量，则生成$q_2$: $\text{A}_{i}=\text{A}(i=1, 2,\dots)$。保证非临时变量在基本块出口时，值是正确的。若$\text{A}_{i}$是临时变量，则不需要生成四元式。

$\bigstar$注意：以主标记参加运算。
\end{itemize}

%-------------------------------------------
\begin{example}
	
求下述语句片段的DAG表示：

$\text{A}=2*3+\text{B}/\text{C}$

$\text{B}=2*3+\text{B}/\text{C}$

$\text{C}=2*3+\text{B}/\text{C}$

解：
\begin{itemize}
\item 第一步，生成四元式序列（不能“自动”优化）

\begin{tabular}{llll}
(1) (*, &2, &3, &$t_{1}$)\\
(2) (/, &B, &C, &$t_{2}$)\\
(3) (+, &$t_{1}$, &$t_{2}$, &$t_{3}$)\\
(4) (=, &$t_{3}$, &\_\_, &A)\\
(5) (*, &2, &3, &$t_{4}$)\\
(6) (/, &B, &C, &$t_{5}$)\\
(7) (+, &$t_{4}$, &$t_{5}$, &$t_{6}$)\\
(8) (=, &$t_{6}$, &\_\_, &B)\\
(9) (*, &2, &3, &$t_{7}$)\\
(10) (/, &B, &C, &$t_{8}$)\\
(11) (+, &$t_{7}$, &$t_{8}$, &$t_{9}$)\\
(12) (=, &$t_{9}$, &\_\_, &C)	
\end{tabular}

\item 第二步，构造优化的DAG

依次读取四元式，根据算法构造DAG。需要注意，访问各结点信息时，按结点号逆序进行。例如读取第10个四元式后，从结点5开始找最新的B和C，从而建立新的结点，旧的B参与运算，且是主标记，要保留。前两个表达式中的B/C是公共表达式，而第三个式子中不是，B的值已经被更新。类似地，读取各个四元式，依据算法构建DAG，最终优化后的DAG图如图\ref{fig:8-7}。

%-------------------------------------------
\begin{figure}[htbp]
\centering
	\begin{tikzpicture}
		\matrix [matrix of nodes,nodes in empty cells,nodes={anchor=west,inner sep=0em,minimum size=1.2em}] (m)
		{
			&\node[circle,draw](n7){7};\\\\
			&&&\node[circle,draw](n6){6};\\\\\\
			&&&\node[circle,draw](n5){5};\\\\
			&&&&&&\node[circle,draw](n4){4};\\\\
			\node[circle,draw](n1){1};&&&&&\node[circle,draw](n2){2};
			&&\node[circle,draw](n3){3};\\
		};
		\node[left=0em of n7]{+};
		\node[right=0em of n7](n7r){\color{red}\bcancel{\color{black}$t_{9}$|C}};
		\node[above=0em of n7r, color=red, yshift=-1.5ex]{C|$t_{9}$};
		\node[left=0em of n6]{/};
		\node[right=0em of n6]{$t_{8}$};
		\node[left=0em of n5]{+};
		\node[right=0em of n5](n5r){\color{red}\bcancel{\color{black}$t_{3}$|A}};
		\node[above=0em of n5r, yshift=-1.5ex,xshift=1em]{\color{red}A|$t_{3}$\color{black},$t_{6}$,B};
		\node[left=0em of n4]{/};
		\node[right=0em of n4]{$t_{2}$|$t_{5}$};
		\node[right=0em of n1,align=center, yshift=-.5em,xshift=-.2em]{6|$t_{1}$,$t_{4}$,$t_{7}$};
		\node[right=-.35em of n2]{B};
		\node[right=-.35em of n3]{C};

		\draw[-] (n7) -- (n6);
		\draw[-] (n5) -- (n6);
		\draw[-] (n5) -- (n1);
		\draw[-] (n5) -- (n4);
		\draw[-] (n4) -- (n2);
		\draw[-] (n4) -- (n3);
		\draw[-] (n3.east) to [out=45,in=-10] (n6.south east);
		\draw[-] (n1.north west) to [out=100,in=-120] (n7.south west);
	\end{tikzpicture}
\caption[]{最终优化后的DAG表示}
\label{fig:8-7}
\end{figure}
%-------------------------------------------

\item 第三步，优化后的四元式序列。按结点编码顺序，依次读取每一结点$n_1$信息，生成相应四元式序列如下。

\begin{tabular}{llll}
(1) (/, &B, &C, &$t_2$)\\
(2) (+, &6, &$t_2$, &A)\\
(3) (=, &A, &\_\_, &B)\\
(4) (/, &A, &C, &$t_8$)\\
(5) (+, &6, &$t_8$, &C)
\end{tabular}

\end{itemize}
\label{ex:8-5}
\end{example}
%-------------------------------------------